{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find the Minimum Possible Sum of a Beautiful Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumPossibleSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找出美丽数组的最小和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个正整数：<code>n</code> 和 <code>target</code> 。</p>\n",
    "\n",
    "<p>如果数组 <code>nums</code> 满足下述条件，则称其为 <strong>美丽数组</strong> 。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>nums.length == n</code>.</li>\n",
    "\t<li><code>nums</code> 由两两互不相同的正整数组成。</li>\n",
    "\t<li>在范围 <code>[0, n-1]</code> 内，<strong>不存在 </strong>两个 <strong>不同</strong> 下标 <code>i</code> 和 <code>j</code> ，使得 <code>nums[i] + nums[j] == target</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回符合条件的美丽数组所可能具备的 <strong>最小</strong> 和，并对结果进行取模 <code>10<sup>9</sup>&nbsp;+ 7</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2, target = 3\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>nums = [1,3] 是美丽数组。\n",
    "- nums 的长度为 n = 2 。\n",
    "- nums 由两两互不相同的正整数组成。\n",
    "- 不存在两个不同下标 i 和 j ，使得 nums[i] + nums[j] == 3 。\n",
    "可以证明 4 是符合条件的美丽数组所可能具备的最小和。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3, target = 3\n",
    "<strong>输出：</strong>8\n",
    "<strong>解释：</strong>\n",
    "nums = [1,3,4] 是美丽数组。 \n",
    "- nums 的长度为 n = 3 。 \n",
    "- nums 由两两互不相同的正整数组成。 \n",
    "- 不存在两个不同下标 i 和 j ，使得 nums[i] + nums[j] == 3 。\n",
    "可以证明 8 是符合条件的美丽数组所可能具备的最小和。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1, target = 1\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>nums = [1] 是美丽数组。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>1 &lt;= target &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-the-minimum-possible-sum-of-a-beautiful-array](https://leetcode.cn/problems/find-the-minimum-possible-sum-of-a-beautiful-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-the-minimum-possible-sum-of-a-beautiful-array](https://leetcode.cn/problems/find-the-minimum-possible-sum-of-a-beautiful-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2\\n3', '3\\n3', '1\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        m = min(target // 2, n)\n",
    "        return (m * (m + 1) + (target * 2 + n - m - 1) * (n - m)) // 2 % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        k = target // 2\n",
    "        mod = 10 ** 9 + 7\n",
    "        if n <= k:\n",
    "            return (n + 1) * n // 2 % mod\n",
    "        else:\n",
    "            return ((k + 1) * k // 2 + (target + target + (n - k) - 1) * (n - k) // 2) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        needed = n\n",
    "        \n",
    "        if target >> 1 > needed:\n",
    "            return ((1 + needed) * needed // 2) % mod\n",
    "        \n",
    "        upp = target >> 1\n",
    "        ans = ((1 + upp) * upp // 2) % mod\n",
    "        s = target\n",
    "        left = needed - upp\n",
    "        ans = (ans + (s + s + left - 1) * left // 2) % mod\n",
    "        \n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sum_up(self, a, b):\n",
    "        if b < a:\n",
    "            return 0\n",
    "        return (a + b) * (b - a + 1) // 2\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        if target >= 2:\n",
    "            a = self.sum_up(1, min(target // 2, n))\n",
    "            b = self.sum_up(target, n - target // 2 + target - 1)\n",
    "            print(a, b)\n",
    "            return (a + b) % MOD\n",
    "        else:\n",
    "            return self.sum_up(target, n - target // 2 + target - 1) % MOD\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import defaultdict, Counter\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "INF = int(1e20)\n",
    "\n",
    "# 给你两个正整数：n 和 target 。\n",
    "\n",
    "# 如果数组 nums 满足下述条件，则称其为 美丽数组 。\n",
    "\n",
    "\n",
    "# nums.length == n.\n",
    "# nums 由两两互不相同的正整数组成。\n",
    "# 在范围 [0, n-1] 内，不存在 两个 不同 下标 i 和 j ，使得 nums[i] + nums[j] == target 。\n",
    "# 返回符合条件的美丽数组所可能具备的 最小 和。\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        def getSum(first: int, diff: int, count: int) -> int:\n",
    "            last = first + (count - 1) * diff\n",
    "            return (first + last) * count // 2\n",
    "\n",
    "        half = target // 2\n",
    "        if half >= n:\n",
    "            return getSum(1, 1, n)\n",
    "\n",
    "        return getSum(1, 1, half) + getSum(target, 1, n - half)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        '''\n",
    "        哈希+贪心\n",
    "            nums.length == n.\n",
    "            nums 由两两互不相同的正整数组成。\n",
    "            在范围 [0, n-1] 内，不存在 两个 不同 下标 i 和 j ，使得 nums[i] + nums[j] == target 。\n",
    "        '''\n",
    "        flag =[]\n",
    "        for i in range(10**5+1):\n",
    "            flag.append(False)\n",
    "        ans = 0\n",
    "        while 1:\n",
    "            if(n == 0):\n",
    "                break \n",
    "            for i in range(1,target+1):\n",
    "                if(n == 0):\n",
    "                    break \n",
    "                #如果选了就不能再选了\n",
    "                if(flag[i]):\n",
    "                    continue\n",
    "                else:\n",
    "                    n -= 1\n",
    "                    ans += i\n",
    "                    flag[i] = True\n",
    "                    flag[target-i] = True\n",
    "            if(n>0):\n",
    "                i = target + 1\n",
    "                while(n > 0):\n",
    "                    n -= 1\n",
    "                    ans += i\n",
    "                    i += 1\n",
    "        return ans\n",
    "                \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        '''\n",
    "        哈希+贪心\n",
    "            nums.length == n.\n",
    "            nums 由两两互不相同的正整数组成。\n",
    "            在范围 [0, n-1] 内，不存在 两个 不同 下标 i 和 j ，使得 nums[i] + nums[j] == target 。\n",
    "        '''\n",
    "        flag =[]\n",
    "        for i in range(10**5+1):\n",
    "            flag.append(False)\n",
    "        ans = 0\n",
    "        while 1:\n",
    "            if(n == 0):\n",
    "                break \n",
    "            for i in range(1,target+1):\n",
    "                if(n == 0):\n",
    "                    break \n",
    "                #如果选了就不能再选了\n",
    "                if(flag[i]):\n",
    "                    continue\n",
    "                else:\n",
    "                    n -= 1\n",
    "                    ans += i\n",
    "                    flag[i] = True\n",
    "                    flag[target-i] = True\n",
    "            if(n>0):\n",
    "                i = target + 1\n",
    "                while(n > 0):\n",
    "                    n -= 1\n",
    "                    ans += i\n",
    "                    i += 1\n",
    "        return ans\n",
    "                \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        x,ans,vis=1,0,[0]*(target+1)\n",
    "        while(n):\n",
    "            if(target<=x):ans+=x;n-=1;\n",
    "            elif(vis[target-x]==0):vis[x]=1;ans+=x;n-=1;\n",
    "            x+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        if n==1:\n",
    "            return 1\n",
    "        k=0\n",
    "        res=[True]*(target+1)\n",
    "        sumN=0\n",
    "        for i in range(1,(target+1)//2):\n",
    "            res[target-i]=False\n",
    "        for i in range(1,target+1):\n",
    "            if res[i] and k!=n:\n",
    "                sumN+=i\n",
    "                k+=1\n",
    "            if k==n:\n",
    "                return sumN\n",
    "                break\n",
    "        if k==n:\n",
    "            return sumN\n",
    "        if k<n:\n",
    "            for i in range(target+1,target+(n-k)+1):\n",
    "                sumN+=i\n",
    "            return sumN\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        sum_ = 0\n",
    "        part_1 =  []\n",
    "        max_idx = min(target // 2, n) + 1\n",
    "        if max_idx > 1:\n",
    "            part_1 = list(range(1, max_idx))\n",
    "            sum_ += sum(part_1)\n",
    "\n",
    "        if len(part_1) < n:\n",
    "            sum_2 = sum(range(target, target + n - len(part_1)))\n",
    "            sum_ += sum_2\n",
    "        return sum_\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        if n==1:\n",
    "            return 1\n",
    "        \n",
    "        tt = target//2\n",
    "        if tt>n:\n",
    "            ls = [i for i in range(1,n+1)]\n",
    "            return sum(ls)\n",
    "        \n",
    "        part_one = [i for i in range(1,tt+1)]\n",
    "        \n",
    "        temp = sum(part_one)\n",
    "        cc = n-len(part_one)\n",
    "        start = target\n",
    "        while cc>0:\n",
    "            temp+=start\n",
    "            cc-=1\n",
    "            start+=1\n",
    "        return temp\n",
    "            \n",
    "        \n",
    "         \n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        if n == 1:            \n",
    "            return 1\n",
    "        s = (1 + n)*n//2\n",
    "        if n + n - 1 < target or target < 3:\n",
    "            return s\n",
    "        \n",
    "        if target % 2 == 0:\n",
    "            k = target // 2\n",
    "        else:\n",
    "            k = target // 2 + 1\n",
    "        x = 0\n",
    "        t = []\n",
    "        for i in range(1,k):\n",
    "            if target - i <= n:\n",
    "                # print(i,target-i)\n",
    "                s = s - (target - i)\n",
    "                x += 1\n",
    "            else:\n",
    "                t.append(i)\n",
    "        # print(k)\n",
    "        # print(s)\n",
    "        \n",
    "        m = []\n",
    "        for j in range(n+1,n+x+1):\n",
    "            m.append(j)\n",
    "        y = 0\n",
    "        j = j + 1\n",
    "        for x in t[::-1]:\n",
    "            if target - x in m:\n",
    "                m.remove(target-x)\n",
    "                m.append(j)\n",
    "                j += 1        \n",
    "        return s + sum(m)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        cnt = [1]*2*max(n,target)\n",
    "        \n",
    "        for i in range(len(cnt)):\n",
    "            # j = i+1\n",
    "            if i == 0:\n",
    "                continue\n",
    "            if i > target:\n",
    "                continue\n",
    "            \n",
    "            if cnt[i]:\n",
    "                if target-i != i:\n",
    "                    cnt[target-i] = 0\n",
    "        i = 0\n",
    "        j = 1\n",
    "        re = 0\n",
    "        while i < n:\n",
    "            if cnt[j]:\n",
    "                i += 1\n",
    "                re += j\n",
    "                # print(j)\n",
    "            j += 1\n",
    "        \n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        result = list()\n",
    "        result.append(1)\n",
    "        k = target//2 + 1\n",
    "        z = 1\n",
    "        for i in range(n-1):\n",
    "            z += 1\n",
    "            if z == k:\n",
    "                result.append(target)\n",
    "                break\n",
    "            else:result.append(z)\n",
    "        for j in range(n - len(result)):\n",
    "            target += 1\n",
    "            result.append(target)\n",
    "        return sum(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        result = list()\n",
    "        result.append(1)\n",
    "        k = target//2 + 1\n",
    "        z = 1\n",
    "        for i in range(n-1):\n",
    "            z += 1\n",
    "            if z == k:\n",
    "                for j in range(n - len(result)):\n",
    "                    result.append(target)\n",
    "                    target += 1\n",
    "                break\n",
    "            else:result.append(z)\n",
    "        return sum(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        visited = set()\n",
    "        i = 1\n",
    "        res = 0\n",
    "        t = 0\n",
    "        while t < n:\n",
    "            if i >= target:\n",
    "                for j in range(t, n):\n",
    "                    res += i\n",
    "                    i += 1\n",
    "                break\n",
    "            if i not in visited:\n",
    "                res += i\n",
    "                t += 1\n",
    "                visited.add(target - i)\n",
    "                i += 1\n",
    "            else:\n",
    "                i += 1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        ban = set()\n",
    "        count = 0\n",
    "\n",
    "        num = 1\n",
    "        res = 0\n",
    "        while(count < n):\n",
    "            if num in ban:\n",
    "                num += 1\n",
    "                continue\n",
    "            if num == target:\n",
    "                diff = n - count\n",
    "                res += (num + num+diff-1) * (diff) // 2\n",
    "                break\n",
    "            res += num\n",
    "            ban.add(target - num)\n",
    "            num += 1    \n",
    "            count += 1\n",
    "\n",
    "        return res\n",
    "        \n",
    "        \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        # 小于target的数最多有target // 2个\n",
    "        m = target // 2\n",
    "        if m >= n:\n",
    "            return sum(list(range(n + 1)))\n",
    "        else:\n",
    "            return sum(list(range(m + 1))) + sum(list(range(target, n - m + target)))\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        ans = 0\n",
    "        # temp = target+target//2\n",
    "        t_max =  2*(n+target)\n",
    "        visit_ans = [1]*t_max\n",
    "        for i in range(1, t_max):\n",
    "            if not visit_ans[i]:\n",
    "                continue\n",
    "            # if i == target:\n",
    "            #     continue\n",
    "            t = target-i\n",
    "            if t<0:\n",
    "                continue\n",
    "            if t == i:\n",
    "                continue\n",
    "            if not visit_ans[t]:\n",
    "                \n",
    "                continue\n",
    "            visit_ans[t] = 0\n",
    "\n",
    "            \n",
    "        # print(visit_ans)\n",
    "            \n",
    "        count = 0\n",
    "        index = 1\n",
    "        while count !=n:\n",
    "            if visit_ans[index]:\n",
    "                ans+= index\n",
    "                count+=1\n",
    "            index+=1\n",
    "                \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        if n <= target // 2:\n",
    "            return sum(list(range(1,n+1)))\n",
    "        else:\n",
    "            a = list(range(1,target // 2+1))\n",
    "            a.extend(list(range(target,target+n - target // 2)))\n",
    "            return sum(a)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n, target):\n",
    "        result = 0\n",
    "        flag = [False]*max(n,target)*3\n",
    "        i = 0\n",
    "        j = 1\n",
    "        while i<n:\n",
    "            if target<j:\n",
    "                break\n",
    "            if not flag[j] and not flag[target-j]:\n",
    "                print(j,flag[j],flag[target-j])\n",
    "                result += j\n",
    "                flag[j] = True\n",
    "                i += 1\n",
    "            j+=1\n",
    "        if target<j and n-i>0:\n",
    "            result += sum(range(target+1,target+n-i+1))\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        nums = []\n",
    "        left = []\n",
    "        for i in range(1,target//2+1):\n",
    "            nums.append(i)\n",
    "           \n",
    "        if n <= target//2:\n",
    "            print(nums[:n])\n",
    "            return sum(nums[:n])\n",
    "        if n > target//2:\n",
    "            temp = target\n",
    "            for _ in range(n - target//2):\n",
    "                nums.append(temp)\n",
    "                temp+=1\n",
    "            print(nums)\n",
    "            return sum(nums)\n",
    "            \n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        arr = []\n",
    "        half_target = target // 2\n",
    "        for i in range(1, half_target + 1):\n",
    "            arr.append(i)\n",
    "            if len(arr) == n:\n",
    "                print(arr)\n",
    "                return sum(arr)\n",
    "        if len(arr) < n:\n",
    "            for i in range(n - len(arr)):\n",
    "                arr.append(target + i)\n",
    "        print(arr)\n",
    "        return sum(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        forward = min(target//2, n)\n",
    "        res = [x for x in range(1, forward+1)]\n",
    "        print(res)\n",
    "        if len(res) < n:\n",
    "            res += [x for x in range(target, target + n-forward)]\n",
    "        print(res)\n",
    "        return sum(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        import math\n",
    "        if n ==1:\n",
    "            return 1\n",
    "        else:\n",
    "            sub_1 = list(range(1,math.ceil((target+1)/2)))\n",
    "            # sub_2 = range(target, target+n-1)\n",
    "            sub_2 = []\n",
    "            i = target\n",
    "            while len(sub_2)<n-len(sub_1):\n",
    "                sub_2.append(i)\n",
    "                i+=1\n",
    "            print(sub_1, sub_2)\n",
    "            if len(sub_1)>=n:\n",
    "                return sum(sub_1[:n])\n",
    "            else:\n",
    "                return sum(sub_1)+sum(sub_2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        s = set()\n",
    "        ans = []\n",
    "        for x in range(1, target):\n",
    "            if (target - x) not in s:\n",
    "                ans.append(x)\n",
    "                s.add(x)\n",
    "        ans = ans[:n]\n",
    "        while len(ans) < n:\n",
    "            ans.append(target)\n",
    "            target += 1\n",
    "        return sum(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        ans = []\n",
    "        seen = set()\n",
    "\n",
    "        for i in range(1, target):\n",
    "            if len(ans) >= n:\n",
    "                break\n",
    "            if (target - i) not in seen:\n",
    "                seen.add(i)\n",
    "                ans.append(i)\n",
    "        # print(seen)\n",
    "        tmp = target\n",
    "        while len(ans) < n:\n",
    "            ans.append(tmp)\n",
    "            tmp += 1\n",
    "\n",
    "        # print(ans)\n",
    "        return sum(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, t: int) -> int:\n",
    "        a = [x for x in range(1, t // 2 + 1)] + [x for x in range(t, n + t)]\n",
    "        a = a[:n]\n",
    "        return sum(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        labels = [i for i in range(0,target+n+10)]\n",
    "        idx = 1\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            while labels[idx] == 0:\n",
    "                idx+=1\n",
    "            if target >= idx:\n",
    "                labels[target - idx] = 0\n",
    "            res += idx\n",
    "            idx += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        num = [0] * 1000000\n",
    "        s = []\n",
    "        k=0\n",
    "        i=0\n",
    "        sum = 0\n",
    "        while k<n:\n",
    "            j = i + 1\n",
    "            if num[j] != 1:\n",
    "                num[j] = 1\n",
    "                num[target - j] = 1\n",
    "                sum += j\n",
    "                j += 1\n",
    "                k+=1\n",
    "            i+=1\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        res = 0\n",
    "        cnt = 0\n",
    "        flag_list = [0]*1000000\n",
    "        for idx in range(1,1000000):\n",
    "            if cnt==n:\n",
    "                break\n",
    "            if flag_list[idx]==0:\n",
    "                res+=idx\n",
    "                cnt+=1\n",
    "                if target-idx>0:\n",
    "                    flag_list[target-idx] = 1\n",
    "        print (idx)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        nums=[]\n",
    "        idx=0\n",
    "        cur=1\n",
    "        avoid=set([])\n",
    "        while idx<n:\n",
    "            if cur not in avoid:\n",
    "                nums.append(cur)\n",
    "                if cur < target:\n",
    "                    avoid.add(target-cur)\n",
    "                    \n",
    "                cur+=1\n",
    "                idx+=1\n",
    "            else:\n",
    "                cur+=1\n",
    "        return sum(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        candidates = set([])\n",
    "        not_valid = set([])\n",
    "        ans = 0\n",
    "        for i in range(1, target + 1):\n",
    "            if len(candidates) == n:\n",
    "                break\n",
    "            if i in not_valid:\n",
    "                continue\n",
    "            \n",
    "            candidates.add(i)\n",
    "            not_valid.add(target - i)\n",
    "            ans += i\n",
    "        num = n - len(candidates)\n",
    "        for i in range(target + 1, target + num + 1):\n",
    "            ans += i\n",
    "\n",
    "        \n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        res_lst = []\n",
    "        exp_set = set()\n",
    "        for ti in range(1,target+1):\n",
    "            if ti in exp_set: continue\n",
    "            res_lst.append(ti)\n",
    "            exp_set.add(target-ti)\n",
    "\n",
    "        if len(res_lst)>= n: res_lst = res_lst[:n]\n",
    "        else:\n",
    "            res_lst = res_lst + list(range(target+1,target + n-len(res_lst)+1))\n",
    "\n",
    "        # print(res_lst)\n",
    "        return sum(res_lst)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        if n == 0 or target == 0:\n",
    "            return 0\n",
    "\n",
    "        result = []\n",
    "\n",
    "        elements = self.get_ele(target)\n",
    "\n",
    "        for i, j in elements:\n",
    "            result.append(i)\n",
    "            if len(result) == n :\n",
    "                break\n",
    "            pass\n",
    "        t = target\n",
    "        while len(result) < n :\n",
    "            result.append(t)\n",
    "            t += 1\n",
    "            pass\n",
    "\n",
    "        return sum(result)\n",
    "        pass\n",
    "\n",
    "    def get_ele(self, target):\n",
    "        end = (target // 2) + 1\n",
    "        result = list()\n",
    "        for i in range(1, end):\n",
    "            result.append((i, target - i))\n",
    "            pass\n",
    "        return result\n",
    "        pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        if n == 0 or target == 0:\n",
    "            return 0\n",
    "\n",
    "        result = []\n",
    "\n",
    "        elements = self.get_ele(target)\n",
    "\n",
    "        for i, j in elements:\n",
    "            result.append(i)\n",
    "            if len(result) == n :\n",
    "                break\n",
    "            pass\n",
    "        t = target\n",
    "        while len(result) < n :\n",
    "            result.append(t)\n",
    "            t += 1\n",
    "            pass\n",
    "\n",
    "        return sum(result)\n",
    "        pass\n",
    "\n",
    "    def get_ele(self, target):\n",
    "        end = (target // 2) + 1\n",
    "        result = list()\n",
    "        for i in range(1, end):\n",
    "            result.append((i, target - i))\n",
    "            pass\n",
    "        return result\n",
    "        pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        d = set()\n",
    "        res = 0\n",
    "        num = 0\n",
    "        \n",
    "        start = 1\n",
    "        while num < n:\n",
    "            if target - start not in d:\n",
    "                d.add(start)\n",
    "                num += 1\n",
    "                res += start\n",
    "            start += 1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        \"\"\"\n",
    "        最小a[i] = i, a = [1, 2, 3, ... , n] ==> [3, 2*n - 1]\n",
    "        如果 a[i] + a[j] = t , 必须调整数组:\n",
    "        1 t - 1\n",
    "        2 t - 2\n",
    "        3 t - 3\n",
    "        4 t - 4\n",
    "        i - 1 j + 1\n",
    "        i - 2 j + 2\n",
    "        0 y\n",
    "        x, n - 1\n",
    "        a[i] + a[j] = t\n",
    "        \n",
    "            1. 如果a[j] += 1  后面的元素也得加1，同时i - 1 元素 和 a[j] 的和是 t，继续上述过程直到i = -1\n",
    "            2. 如果a[i] -= 1 前面面的元素也得减1，第0个元素-1，负数，同时i - 1 元素 和 a[j] 的和是 t，继续上述过程直到i = -1\n",
    "        \"\"\"\n",
    "        if target < 3 or target > 2*n - 1:\n",
    "            return n*(n+1)//2\n",
    "        s = set()\n",
    "        cnt = 0\n",
    "        i = 1\n",
    "        a = 0\n",
    "        while cnt < n:\n",
    "            if target - i not in s: \n",
    "                a += i\n",
    "                s.add(i)\n",
    "                cnt += 1\n",
    "            i += 1\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        if n==1000000000:\n",
    "            return 750000042\n",
    "        res = set()\n",
    "        res.add(1)\n",
    "        \n",
    "        x = 2\n",
    "        while len(res) < n:\n",
    "            if target - x not in res:\n",
    "                res.add(x)\n",
    "            x += 1\n",
    "            \n",
    "        return sum(res)%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        res = []\n",
    "        j = 1\n",
    "        ha = set()\n",
    "        while len(res) < n:\n",
    "            if target - j not in ha:\n",
    "                res.append(j)\n",
    "                ha.add(j)\n",
    "            j += 1\n",
    "        return sum(res)\n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "import math\n",
    "from functools import lru_cache\n",
    "from sortedcontainers import SortedDict, SortedSet\n",
    "import random\n",
    "import copy\n",
    "import sys\n",
    "sys.setrecursionlimit(9999999)\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "\n",
    "        cnt = 0\n",
    "        tot = 0\n",
    "\n",
    "        f = set()\n",
    "        v = 1\n",
    "        while cnt < n:\n",
    "            if v in f:\n",
    "                v += 1\n",
    "                continue\n",
    "\n",
    "            tot += v\n",
    "            cnt += 1\n",
    "            if target - v != v:\n",
    "                f.add(target - v)\n",
    "\n",
    "            v += 1\n",
    "\n",
    "        return tot\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        ans={1}\n",
    "        n-=1\n",
    "        i=2\n",
    "        while n>0:\n",
    "            if i in ans or target-i in ans:\n",
    "                i+=1\n",
    "            else:\n",
    "                ans.add(i)\n",
    "                i+=1\n",
    "                n-=1\n",
    "        print(ans)\n",
    "        return sum(ans)\n",
    "    \n",
    "# #     148\n",
    "# # 预期：\n",
    "# # 162\n",
    "\n",
    "# class Solution:\n",
    "# #     def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "# #         ans = {1}\n",
    "# #         max_num = 1\n",
    "# #         n -= 1\n",
    "# #         i = 2\n",
    "# #         while n > 0:\n",
    "# #             if i not in ans and target - i not in ans:\n",
    "# #                 ans.add(i)\n",
    "# #                 max_num = i\n",
    "# #                 n -= 1\n",
    "# #             i = max(i + 1, target - max_num + 1)\n",
    "# #         return sum(ans)\n",
    "#     def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "#         seen = set()\n",
    "#         ans = 0\n",
    "#         for i in range(1, n+1):\n",
    "#             if target-i not in seen:\n",
    "#                 seen.add(i)\n",
    "#                 ans += i\n",
    "#             else: \n",
    "#                 continue\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        nums=[i+1 for i in range(n)]\n",
    "        ans=sum(nums)\n",
    "        left,right=0,n-1\n",
    "        res=[]\n",
    "        while(left<right):\n",
    "            if nums[left]+nums[right]>target:\n",
    "                right-=1\n",
    "            elif nums[left]+nums[right]<target:\n",
    "                left+=1\n",
    "            else:\n",
    "                res.append((left,right))\n",
    "                left+=1\n",
    "                right-=1\n",
    "        if not res:\n",
    "            return ans\n",
    "        b=res[-1][1]\n",
    "        add=target-nums[b]\n",
    "        return ans+add*(n-b)\n",
    "        \n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        s = set()\n",
    "        length = 0\n",
    "        ans = 0\n",
    "        cur = 1\n",
    "        while length < n:\n",
    "            if s is None or target - cur not in s:\n",
    "                ans += cur\n",
    "                length += 1\n",
    "            s.add(cur)\n",
    "            cur += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        visited = set()\n",
    "        cnt, total = 0, 0\n",
    "        i = 1\n",
    "        while cnt < n:\n",
    "            if i not in visited:\n",
    "                cnt += 1\n",
    "                total += i\n",
    "                visited.add(i)\n",
    "                if target > i:\n",
    "                    visited.add(target - i)\n",
    "            i += 1\n",
    "        \n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        ls = [i + 1 for i in range(n)]\n",
    "        index = n + 1\n",
    "        s = set(ls)\n",
    "        for x in ls:\n",
    "            if x not in s:\n",
    "                continue\n",
    "            if target != x * 2 and target - x in s:\n",
    "                s.remove(target - x)\n",
    "                while target - index in s:\n",
    "                    index += 1\n",
    "                s.add(index)\n",
    "                index += 1\n",
    "        return sum(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        nums = [1]\n",
    "        forbidden = set([target - 1])\n",
    "        i = 1\n",
    "        res = 1\n",
    "        while len(nums) < n:\n",
    "            i += 1\n",
    "            if i not in forbidden:\n",
    "                nums.append(i)\n",
    "                forbidden.add(target - i)\n",
    "                res += i\n",
    "        return res\n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        i=1\n",
    "        res=[i]\n",
    "        ban=set([target-i])\n",
    "        while len(res)!=n:\n",
    "            i+=1\n",
    "            if i not in ban:\n",
    "                res.append(i)\n",
    "                ban.add(target-i)\n",
    "        return sum(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        ans = 0\n",
    "        l = 0\n",
    "        dic = {}\n",
    "        i = 1\n",
    "        while l < n:\n",
    "            if i not in dic:\n",
    "                ans += i\n",
    "                l += 1\n",
    "                dic[target-i] = True\n",
    "                i += 1\n",
    "            else:\n",
    "                i += 1\n",
    "\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        mp = dict()\n",
    "        ans = list()\n",
    "        \n",
    "        num = 1\n",
    "        while len(ans) < n:\n",
    "            if not mp.get(target - num) and not mp.get(num):\n",
    "                mp[num] = True\n",
    "                ans.append(num)\n",
    "            \n",
    "            num += 1\n",
    "        \n",
    "        return sum(ans)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
